package lc;
import org.junit.*;
import util.*;
public class Ex86 {
    class Solution {
        public ListNode partition(ListNode head, int x) {
            ListNode pre = new ListNode(0), post = new ListNode(0);
            ListNode r1 = pre,  r3 = post, cur = head, tmp;
            while (cur != null) {
                tmp = cur.next;
                if (cur.val < x) {
                    pre.next = cur;
                    pre = pre.next;
                    pre.next = null;
                } else {
                    post.next = cur;
                    post = post.next;
                    post.next = null;
                }
                cur = tmp;
            }
            ListNode res = new ListNode(0), result = res;
            if (pre != r1) {
                res.next = r1.next;
                res = pre;
            }
    
            if (post != r3) {
                res.next = r3.next;
            }
    
            return result.next;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{1,4,3,2,5,2};
        ListNode head = ListNode.newListNodeFromArray(nums);
        System.out.println(s.partition(head, 3));
    }
}
